package com.yeung.alo

/**
  * 汉罗塔
  *
  * 递归实现方案
  */
object Hanoi {
  var count = 0;

  def main(args: Array[String]): Unit = {
    hanoi(3, 'x', 'y', 'z')
  }

  /**
    *
    * @param n   要移动的圆盘编号
    * @param x   起始移动塔
    * @param y 辅助塔
    * @param z   目标塔
    */
  def hanoi(n: Int, x: Char, y: Char, z: Char): Unit = {
    if (n == 1)
    //将编号为1的圆盘从x移动到z
      move(1, x, z)
    else {
      //1. 将编号为1到n-1的圆盘从x移动到y, z作为辅助塔
      hanoi(n - 1, x, z, y)
      //2. 将编号为n的圆盘移动到z塔
      move(n, x, z)
      //3. 将y上编号为1到n-1的圆盘移动到z塔, x作为辅助塔
      hanoi(n - 1, y, z, x)

    }
  }

  /**
    *
    * @param x 起始塔
    * @param n 移动的圆盘的编号
    * @param z 目标塔
    */
  def move(n: Int, x: Char, z: Char): Unit = {
    count += 1
    println(s"move ${n}, from ${x} to ${z}")
  }

}
